package algorithm.tree;

import algorithm.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode
 * 113. Path Sum II
 *
 * https://leetcode.com/problems/path-sum-ii/
 * Difficulty : Medium
 * Topic: Tree, DFS
 * Interview Company: 阿里
 *
 * 说明：
 * 给一个数，给一个sum，从根到叶子节点，找出路径和恰好为sum的，路径集合
 * Created by yzy on 2020-04-09 23:40
 */
public class PathSumII {

    public static void main(String[] args) {
        Integer[] nodes = new Integer[]{5,4,8,11,null,13,4,7,2,null,null,null,null,5,1};    // sum=22
        Integer[] nodes_2 = new Integer[]{-2,null,-3};      // sum=-5;

        List<List<Integer>> lists = pathSum(TreeNode.getTreeNode(nodes), 22);
        System.out.println(lists);
        List<List<Integer>> lists_2 = pathSum(TreeNode.getTreeNode(nodes_2), -5);
        System.out.println(lists_2);
    }


    /**
     * DFS思路,就不细讲了
     * RumTime: 1ms, 99.96%
     * Memory: 39.8MB, 19.69%
     * @param root
     * @param sum
     * @return
     */
    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmpList = new ArrayList<>();
        findPath(result, tmpList, root, sum);
        return result;
    }

    private static void findPath(List<List<Integer>> result, List<Integer> tmpList, TreeNode treeNode, int sum){
        if(treeNode==null){
            return;
        }

        int nextSum = sum - treeNode.val;
        tmpList.add(treeNode.val);
        if(nextSum == 0 && treeNode.left==null && treeNode.right==null){
            result.add(new ArrayList<>(tmpList));
        }else{
            findPath(result, tmpList, treeNode.left, nextSum);
            findPath(result, tmpList, treeNode.right, nextSum);
        }
        tmpList.remove(tmpList.size()-1);
    }
}
